Double-layer capacitors capable of operating at extremely low temperatures (e.g., as low as -80.degree. C.) are disclosed. Electrolyte solutions combining a base solvent (e.g., acetonitrile) and a cosolvent are employed to lower the melting point of the base electrolyte. Example cosolvents include methyl formate, ethyl acetate, methyl acetate, propionitrile, butyronitrile, and 1,3-dioxolane. A quaternary ammonium salt including at least one of triethylmethylammonium tetrafluoroborate (TEMATFB) and spiro-(1,1')-bipyrrolidium tetrafluoroborate (SBPBF.sub.4), is used in an optimized concentration (e.g., 0.10 M to 0.75 M), dissolved into the electrolyte solution. Conventional device form factors and structural elements (e.g., porous carbon electrodes and a polyethylene separator) may be employed.